package j20251014;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    int sum;
    int path;
    public int subsetXORSum(int[] nums) {
        sum=0;
        path=0;
        dfs(nums,0);
        return sum;
    }

    public void dfs(int[] nums,int pos){
        sum+=path;
        for(int i=pos;i<nums.length;i++){
            path^=nums[i];
            dfs(nums,i+1);
            //回溯
            path^=nums[i];
        }
    }

    List<List<Integer>> ret;
    List<Integer> path0;
    boolean[] check;
    public List<List<Integer>> permuteUnique(int[] nums) {
        ret=new ArrayList<>();
        path0=new ArrayList<>();
        check=new boolean[nums.length];
        Arrays.sort(nums);
        dfs0(nums,0);
        return ret;
    }
    public void dfs0(int[] nums,int pos){
        if(pos==nums.length){
            ret.add(new ArrayList<>(path0));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(check[i]==false&&(i==0||nums[i]!=nums[i-1]||check[i-1]==true)){//剪枝
                path0.add(nums[i]);
                check[i]=true;
                dfs(nums,pos+1);
                //回溯
                path0.remove(path0.size()-1);
                check[i]=false;
            }
        }
    }
}
